package newcoder_exp.justPractise;

import org.junit.Test;

public class NC156 {
    //找出唯一出现一次的数，其他都出现k次
    int[] ds = new int[32];
    public int foundOnceNumber (int[] arr, int k) {
        for (int i = 0; i < arr.length; i++) {
            add(arr[i]);
        }
        int sum = 0;
        for (int i = 0; i < 32; i++) {
            ds[i] %= k;
            sum += twoP(i) * ds[i];
        }
        return sum;
    }

    /* 
        将num的每个二进制位加到对应的ds位置上
    */
    public void add(int num) {
        int idx = 0;
        while (num != 0) {
            if ((num & 1) == 1) {
                ds[idx]++;
            }
            idx++;
            num >>>= 1;
        }
    }

    public int twoP(int n) {
        int sum = 1, t = 2;
        while(n != 0) {
            if ((n & 1) == 1) {
                sum *= t;
            }
            t *= t;
            n >>>= 1;
        }
        return sum;
    }

    @Test
    public void test() {
        // int nums[] = {5,4,1,1,5,1,5 };
        int nums[] = {5,4,3,4,5 };
        int on3 = foundOnceNumber(nums, 2);
        System.out.println(on3);
    }
}
